# N,V,v,w=3,4,[4,2,3],[4,2,3]
N,V,v,w=3,5,[4,2,3],[4,2,3]
def knapsack(N,V,v,w):
    #设置dp状态矩阵
    #i:选取第i个物品
    #j:可用容量
    #dp[i][j]:在选择第i个物品时，可用容量为j的情况下，最大的收益
    dp=[[0 for _ in range(V+1)] for _ in range(N)]
    #先处理第一行
    for i in range(V+1):
        if i==0:
            dp[0][i]=0
        else:
            if i>=v[0]:
                dp[0][i]=w[0]
            else:
                dp[0][i]=0

    for i in range(1,N):
        for j in range(V+1):
            if j==0:
                dp[i][j]=0
            else:
                if j>=v[i]:
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
                else:
                    dp[i][j]=dp[i-1][j]
    return dp[N-1][V]

#空间压缩到2维
def knapsack2(N,V,v,w):
    #设置dp状态矩阵
    #i:选取第i个物品
    #j:可用容量
    #dp[i][j]:在选择第i个物品时，可用容量为j的情况下，最大的收益
    dp=[[0 for _ in range(V+1)] for _ in range(2)]
    #先处理第一行
    for i in range(V+1):
        if i==0:
            dp[0][i]=0
        else:
            if i>=v[0]:
                dp[0][i]=w[0]
            else:
                dp[0][i]=0

    for i in range(1,N):
        for j in range(V+1):
            if j==0:
                dp[i&1][j]=0
            else:
                if j>=v[i]:
                    dp[i&1][j]=max(dp[(i-1)&1][j],dp[(i-1)&1][j-v[i]]+w[i])
                else:
                    dp[i&1][j]=dp[(i-1)&1][j]
    return dp[(N-1)&1][V]
def  Knapsack3(N,V,v,w):
    #设置dp状态转移矩阵
    dp=[0 for _ in range(V+1)]

    for i in range(0,N):
        j=V
        while j>0:
            if j>=v[i]:
                dp[j]=max(dp[j-v[i]]+w[i],dp[j])
            else:
                dp[j]=dp[j]
            j-=1
    return dp[V]


print(Knapsack3(N,V,v,w))